package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (null == root) {
            return res;
        }

        Deque<TreeNode> dq = new LinkedList<>();
        TreeNode stopSign = new TreeNode(0);
        dq.addLast(root);
        dq.addLast(stopSign);

        List<Integer> curLevel = new ArrayList<>();
        while (!dq.isEmpty() && !(dq.size() == 1 && dq.peek() == stopSign)) {
            //travel cur level
            TreeNode cur = dq.removeFirst();
            if (cur == stopSign) {
                //already meet current level edge.
                dq.addLast(stopSign);
                res.add(curLevel);
                curLevel = new ArrayList<>();
                continue;
            }

            curLevel.add(cur.val);
            if (cur.left != null) dq.addLast(cur.left);
            if (cur.right != null) dq.addLast(cur.right);
        }

        res.add(curLevel);
        return res;
    }


    public static void main(String[] args) {
        LC102 an = new LC102();
        TreeNode root = TreeNode.createTree("3,9,20,null,null,15,7");
        System.out.println(an.levelOrder(root));
    }
}
